/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-14 17:26:12
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-14 17:26:38
 * @FilePath: /lzb/GiteeCode/algorithm/优选算法37.消失的两个数字(hard).cpp
 * @Description: 题目链接: https://leetcode.cn/problems/missing-two-lcci
 */
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1. 数学方法,求和相减,得到缺失两数的和sum,依据中间值mid将两数分为大于mid和小于等于mid
        // 分别将所有小于等于mid的值求和相减得到第一个数a,sum-a得到缺失的b
        // int sum_notmiss = 0, sum_miss = 0;
        // for(int i = 1; i <= nums.size() + 2; i++) sum_notmiss += i;
        // for(const auto& x : nums) sum_miss += x;
        // int sum = sum_notmiss - sum_miss;
        // int mid = sum / 2;
        // sum_notmiss = 0,sum_miss = 0;
        // for(int i = 1; i <= nums.size() + 2; i++)
        //     if(i <= mid) sum_notmiss += i;
        // for(const auto& x : nums) 
        //     if(x <= mid) sum_miss += x;
        // int v1 = sum_notmiss - sum_miss;
        // int v2= sum - v1;
        // return {v1,v2};

        // 2. 哈希统计
        // unordered_map<int,int> hash;
        // vector<int> ret;
        // for(int i = 0; i < nums.size(); i++) hash[nums[i]]++;
        // for(int i = 1; i <= nums.size() + 2; i++) {
        //     if(hash[i] == 0) ret.push_back(i);
        // }
        // return ret;
        
        // 3. 位运算
        // 将[1,n+2]的数和数组中的数全部异或,其余抵消,只剩两个出现一次的数
        // 提取出最右侧1的位,依据这个条件将数组中数分为两组,分别异或到两个值上,找出两个结果
        int tmp = 0;
        for(int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
        for(const auto& x : nums) tmp ^= x;
        int flag = tmp & (-tmp); // 提取最右侧的1位(不同位)
        int v1 = 0, v2 = 0;
        for(const auto& x : nums) {
            if(x & flag) v1 ^= x;
            else v2 ^= x;
        }
        for(int i = 1; i <= nums.size() + 2; i++) {
            if(i & flag) v1 ^= i;
            else v2 ^= i;
        }
        return {v1,v2};
    }
};